Mô men tần số

Mô men tần số thứ k {\displaystyle k} của một tập hợp các tần số a {\displaystyle \mathbf {a} } được định nghĩa là F k ( a ) = ∑ i = 1 n a i k {\displaystyle F_{k}(\mathbf {a} )=\sum _{i=1}^{n}a_{i}^{k}} .

Mô men thứ nhất F 1 {\displaystyle F_{1}} đơn giản là tổng tất cả các tần số(nghĩa là tổng toàn bộ). Mô men thứ hai F 2 {\displaystyle F_{2}} được dùng để tính nhiều chỉ số thống kê của dữ liệu, chẳng hạn như hệ số Gini. F ∞ {\displaystyle F_{\infty }} được định nghĩa là tần số của phần tử phổ biến nhất.

Bài báo của Alon, Matias & Szegedy (1999)Lỗi harv: không có mục tiêu: CITEREFAlonMatiasSzegedy1999 (trợ giúp) mở đầu nghiên cứu về việc ước lượng các mô men tần số của dòng dữ liệu.

Phần tử phổ biến

Bài toán này yêu cầu tìm tất cả các phần tử xuất hiện nhiều lần trong dòng dữ liệu, chẳng hạn ít nhất 1% của toàn bộ dữ liệu. Một vài thuật toán cho bài toán này bao gồm

• Thuật toán Karp, Papadimitriou & Shenker (2003)Lỗi harv: không có mục tiêu: CITEREFKarpPapadimitriouShenker2003 (trợ giúp)
• Thuật toán Count-Min[6]
• Thuật toán Count-sketch[7]

Đếm số phần tử khác nhau

Bài toán này yêu cầu đếm số phần tử khác nhau xuất hiện trong dòng dữ liệu (đôi khi gọi là mô men F 0 {\displaystyle F_{0}} dù tên gọi này không chính xác về mặt toán học). Thuật toán đầu tiên cho bài toán này là của Flajolet và Martin, và thuật toán tốt nhất hiện nay về thời gian và bộ nhớ là của D. Kane, J. Nelson và D. Woodruff.[8] Nó dùng bộ nhớ O(ε^2 + log d) và thời gian cập nhật là O(1) trong trường hợp xấu nhất.

Entropy

Entropy (thực nghiệm) của tập hợp các tần số a {\displaystyle \mathbf {a} } được định nghĩa là H ( a ) = ∑ i = 1 n a i m log ⁡ a i / m {\displaystyle H(\mathbf {a} )=\sum _{i=1}^{n}{\frac {a_{i}}{m}}\log {a_{i}/m}} , trong đó m = ∑ i = 1 n a i {\displaystyle m=\sum _{i=1}^{n}a_{i}} .

Việc ước lượng hàm số này cho dòng dữ liệu là chủ đề của nhiều bài báo chẳng hạn như của Lall và đồng nghiệp (2006)Lỗi harv: không có mục tiêu: CITEREFLallSekarOgiharaXu2006 (trợ giúp) hay Chakrabarti, Cormode & McGregor (2010)Lỗi harv: không có mục tiêu: CITEREFChakrabartiCormodeMcGregor2010 (trợ giúp).